<html>
	<head>
		<title>is point in triangle ----- by qq.d.y</title>
		<script src="util.js"></script>
		<script>
			function rand(min, max)   { return Math.random() * (max - min) + min; }
			var gl, W, H, g2d;
			var pt = [];
			var vel = [];
			var tri = [];
			var M_AREA = 0, M_SAMESIDE = 1;
			function init() {
				W = document.getElementById('canvas').width;
				H = document.getElementById('canvas').height;
				gl = document.getElementById('canvas').getContext('experimental-webgl');
				if (!gl)   alert('please do not use fuck IE...');
				gl.clearColor(0,0,0,1);

				g2d = new G2D(gl, W, H);
				
				// add triangles
				tri.push([10,10, 300,200, 240,20, [0,1,0]]);
				tri.push([50,460, 50,260, 300,360, [0,1,0]]);
				tri.push([350,300, 550,400, 620,280, [0,1,0]]);
				tri.push([380,180, 610,220, 520,30, [0,1,0]]);
				// add point
				pt = [W/2, H/2];
				vel = [rand(1,3), rand(1,3)];
				
				setTimeout(loop, 30);
			}
			function tri_area(p1, p2, p3) {   // calculate triangle area by coordinates , see Wiki for detail
				return 0.5 * Math.abs((p1[0]-p3[0]) * (p2[1]-p1[1]) - (p1[0]-p2[0]) * (p3[1]-p1[1]));
			}
			function is_float_equal(a, b)   { return Math.abs(a - b) < 0.00001; }
			function v3cross(a, b)   { return [a[1]*b[2] - a[2]*b[1], a[2]*b[0] - a[0]*b[2], a[0]*b[1] - a[1]*b[0]]; }
			function v3dot(a, b)     { return a[0]*b[0] + a[1]*b[1] + a[2]*b[2]; }
			function is_same_side(p1,p2, a,b) {
				var base = [b[0]-a[0], b[1]-a[1], b[2]-a[2]];
				var v1 = [p1[0]-a[0], p1[1]-a[1], p1[2]-a[2]];
				var v2 = [p2[0]-a[0], p2[1]-a[1], p2[2]-a[2]];
				var cp1 = v3cross(base, v1);
				var cp2 = v3cross(base, v2);
				if (v3dot(cp1, cp2) >= 0)   return true;
				return false;
			}
			function loop() {
				// which method should I use
				var method;
				if (document.getElementById('utac').checked)   method = M_AREA;
				else if (document.getElementById('ussm').checked)   method = M_SAMESIDE;
//console.log(method);				
			
				g2d.begin();
				
				// is point in triangle
				if (method === M_AREA) {
					for (var i in tri) {
						var t = tri[i];
						var p1 = [t[0], t[1]];
						var p2 = [t[2], t[3]];
						var p3 = [t[4], t[5]];
						var area_1 = tri_area(p1, p2, p3);
						var area_2 = tri_area(pt, p1, p2);
						area_2 += tri_area(pt, p2, p3);
						area_2 += tri_area(pt, p1, p3);
						if (is_float_equal(area_1, area_2)) {
							t[6] = [1,0,0];
						} else {
							t[6] = [0,1,0];
						}
					}
				} else if (method === M_SAMESIDE) {
					for (var i in tri) {
						var t = tri[i];
						var p1 = [t[0], t[1], 0];   // expand to 3D vector
						var p2 = [t[2], t[3], 0];   // because we need z coord
						var p3 = [t[4], t[5], 0];
						var p = [pt[0], pt[1], 0];
						if (is_same_side(p,p1,p2,p3) && is_same_side(p,p2,p1,p3) && is_same_side(p,p3,p1,p2))   t[6] = [1,0,0];
						else   t[6] = [0,1,0];
					}
				}
				
				// update and draw circle
				pt[0] += vel[0];
				pt[1] += vel[1];
				if (pt[0] < 0 || pt[0] > W)   vel[0] = -vel[0];
				if (pt[1] < 0 || pt[1] > H)   vel[1] = -vel[1];
				g2d.circle(pt[0], pt[1], 3, [1,0,0], 0.4);
				// draw triangles
				for (var i in tri) {
					var t = tri[i];
					g2d.line(t[0],t[1], t[2],t[3], t[6], 0.5);
					g2d.line(t[2],t[3], t[4],t[5], t[6], 0.5);
					g2d.line(t[4],t[5], t[0],t[1], t[6], 0.5);
				}
				
				g2d.end();
				
				setTimeout(loop, 30);
			}
		</script>
	</head>
	<body onload='init()'>
		<canvas id="canvas" style="border:none;" width='640' height='480'></canvas>
		<br><br/>
		<input type="radio" name='method' id='utac' checked />use triangle area compare<br/>
		<input type="radio" name='method' id='ussm' />use same side method<br/>
	</body>
</html>